package com.sali.DP;

/**
 * @author sali
 * @date 2025/5/4 20:00
 */
public class LeetCode_96 {

    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int right = 2; right <= n; right++) {
            for (int left = 1; left <= right; left++) {
                dp[right] += dp[left - 1] * dp[right - left];
            }
        }

        return dp[n];
    }

}
